// https://leetcode.cn/problems/missing-number/description/

// 算法思路总结：
// 1. 使用异或运算特性：a ^ a = 0, a ^ 0 = a
// 2. 将0到n的所有数字与数组元素进行异或
// 3. 成对数字相互抵消，最终结果即为缺失数字
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        int ret = 0, n = nums.size();
        for (int i = 0 ; i < n ; i++)
        {
            ret ^= i + 1;
            ret ^= nums[i];
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {3,0,1}, v2 = {9,6,4,2,3,5,7,0,1};

    Solution sol;
    cout << sol.missingNumber(v1) << endl;
    cout << sol.missingNumber(v2) << endl;

    return 0;
}